package demo.algorithm;

import java.util.Arrays;

import org.junit.Test;

/**
 * 斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda
 * Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1,
 * F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从1963年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。
 *
 *
 * <h1>与黄金分割 关系</h1>
 * 有趣的是，这样一个完全是自然数的数列，通项公式却是用无理数来表达的。而且当n趋向于无穷大时，前一项与后一项的比值越来越逼近黄金分割0.618（或者说后一项与前一项的比值小数部分越来越逼近0.618）。
 * 1÷1=1，1÷2=0.5，2÷3=0.666...，3÷5=0.6，5÷8=0.625…………，55÷89=0.617977……………144÷233=0.618025…46368÷75025=0.6180339886…...
 * 越到后面，这些比值越接近黄金比.
 */
public class Fibonacci {

    @Test
    public void test() {
        for (int n = 0; n < 1000; n++) {
            System.out.println(n + " >>" + fibonacciA(n));
        }

        for (int n = 0; n < 1000; n++) {
            System.err.println(n + " >>" + fibonacciB(n));
        }
    }

    @Test
    public void fibonacciC() {
        long[] array = new long[100];
        array[0] = 0;
        array[1] = 1;
        for (int n = 2; n < 100; n++) {
            array[n] = array[n - 1] + array[n - 2];
        }
        System.out.println(Arrays.toString(array));
    }

    /**
     * FOR循环，快
     * 
     * @param n
     * @return
     */
    public static long fibonacciA(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        long a = 0, b = 1, c = 1;

        for (int i = 3; i <= n; i++) {
            a = b;
            b = c;
            c = a + b;
        }
        return c;
    }

    /**
     * 递归算法，慢！
     * 
     * @param n
     * @return
     */
    public static long fibonacciB(int n) {
        if (n <= 0) {
            return 0L;
        } else if (n == 1) {
            return 1L;
        } else {
            return fibonacciB(n - 1) + fibonacciB(n - 2);
        }
    }

}
